﻿using System;
using System.Collections.Generic;
using System.Text;

using RSEngine.Math;
using RSEngine.Helper.Collection;

#region Copyright (c) 2006, 2007, 2008, 2009 Render Studio Foundation. All rights reserved.

/*
 Copyright (c) 2006, 2007, 2008, 2009 Render Studio Foundation. All rights reserved.
 This work is copyrighted in its entirety. Permission to use "Render Studio"
 material may be granted only after we receive a written request from you,
 and you receive written permission from us.

 While Render Studio Foundation provides the information herein to anyone,
 we retain copyright on all code, text, graphic images, and other content.
 This means that you may not distribute the code, the text or graphics to others without the
 express written permission of Render Studio Foundation; "mirror" this information on your server
 without our permission; or modify or reuse the code, text or graphics on our servers.
 You may print copies of the information for your own personal use; and, you may reference
 the Service from your own documents. Any commercial use of this material is prohibited without
 the written permission of Render Studio Foundation. In all copies of this information, you must
 retain this notice and any other copyright notices originally included with such information.

 This material may be protected by U.S. and International Copyright laws, and you are legally
 bound by the copyright notices on those systems.

 "Render Studio" logos and other official symbols or graphics may not be used in connection with any
 product or service that has not been expressly authorized in advance in writing or in any manner
 that is likely to cause confusion among the users of this or other Web sites or among the public.
 All other seals, graphics or trademarks of organizations not affiliated with Render Studio Foundation
 that appear on this site are the property of their respective owners.

 Render Studio Foundation reserve all other rights. 
*/

#endregion

#region Render Studio Source Code Licence

/*
This license governs use of the Render Studio software. If you use the software, you accept this license. If you do not accept the license, do not use the software.

1. Summary

The source code is made available to view for reference purposes or to contribute to the project only. Developers may not distribute or modify the code for commercial or non-commercial purposes without express Agreement of Render Studio Foundation.

2. Definitions

The terms "reproduce," "reproduction," and "distribution" have the same meaning here as under U.S. copyright law.
"Licensor" means the foundation "Render Studio Foundation".
"You" means the licensee of the software, who is not engaged in designing, developing, or testing other software, that has the same or substantially the same features or functionality as the software.
"Your company" means the company you worked for when you downloaded the software.
"Reference use" means use of the software within your company as a reference, in read only form, for the sole purposes of debugging and maintaining your products. For clarity, "reference use" does NOT include (a) the right to use the software for purposes of designing, developing, or testing other software, that has the same or substantially the same features or functionality as the software, and (b) the right to distribute the software outside of your company.
"Licensed patents" means any Licensor patent claims which read directly on the software as distributed by the Licensor under this license.

3. Grant of Rights

(A) Copyright Grant- Subject to the terms of this license, the Licensor grants you a non-transferable, non-exclusive, worldwide, royalty-free copyright license to reproduce the software for reference use.
(B) Patent Grant- Subject to the terms of this license, the Licensor grants you a non-transferable, non-exclusive, worldwide, royalty-free patent license under licensed patents for reference use.
4. Limitations
(A) No Trademark License- This license does not grant you any rights to use the Licensor's name, logo, or trademarks.
(B) If you begin patent litigation against the Licensor over patents that you think may apply to the software (including a cross-claim or counterclaim in a lawsuit), your license to the software ends automatically.
(C) The software is licensed "as-is." You bear the risk of using it. The Licensor gives no express warranties, guarantees or conditions. You may have additional consumer rights under your local laws which this license cannot change. To the extent permitted under your local laws, the Licensor excludes the implied warranties of merchantability, fitness for a particular purpose and non-infringement.
 */

#endregion

namespace RSEngine.Core
{

    #region MeshOptimization

    public enum MeshOptimization
    {
        /// <summary>
        /// Faster version, do the minimum.
        /// </summary>
        Light,

        /// <summary>
        /// Fast, but can generate more vertices than in the existing version.
        /// </summary>
        Fast,

        /// <summary>
        /// Full mesh optimization, it is a HEAVY operation O(N*N-1)
        /// </summary>
        Full
    }

    #endregion

    /// <summary>
    /// This class holds the data used to represent a discrete 3-dimensional object.
    ///  
    /// MeshGeometry data usually contains more than just vertices and triangle information;
    /// it also includes references to materials
    /// 
    /// It is important to notice that there exists a list of sub meshes because
    /// each one can have different materials.
    /// </summary>
    sealed public class MeshGeometry : Geometry
    {

        #region Variables

        /// <summary>
        /// The vertices of the triangles.
        /// </summary>
        public RSList<Vertex> Vertices = new RSList<Vertex>(3);

        /// <summary>
        /// A list of indices, grouped by 3;
        /// </summary>
        public RSList<int> Indices = new RSList<int>(3);

        /// <summary>
        /// A list of integers, each specifying the number of vertices for each polygon;
        /// </summary>
        public RSList<int> VerticesPerPolygon = new RSList<int>(1);

        /// <summary>
        /// If false, we have to compute the normals.
        /// </summary>
        public bool IsUpdatedNormal = false;

        /// <summary>
        /// If false, we have to update the vertex winding order.
        /// </summary>
        public bool IsUpdatedVertexWinding = true;

        /// <summary>
        /// Used when all the faces have the same number of vertices.
        /// </summary>
        public bool IsOptimized = false;

        // Optimization
        public int _facesCount = -1;
        public int _verticesPerFace = -1;

        //----
        private int _LOD = -1;

        //---- Faces and edges
        private RSList<FaceProxy> _faces = null;

        #endregion

        #region Constructor

        public MeshGeometry(RSBase parent)
            : base(parent)
        {
        }


        public MeshGeometry(RSBase parent, int verticesPerFaces)
            : base(parent)
        {
            _verticesPerFace = verticesPerFaces;
            VerticesPerPolygon = null;
        }

        #endregion

        #region Properties

        public override RSType Type
        {
            get { return RSType.MeshGeometry; }
        }

        /// <summary>
        /// Returns the number of vertices for a specific face.
        /// </summary>
        public int VerticesPerFace(int faceIndex)
        {
            if (_verticesPerFace > -1)
                return _verticesPerFace;
            return VerticesPerPolygon[faceIndex];
        }

        /// <summary>
        /// If true, it mean that all the polygons have the same number of edges/vertices.
        /// </summary>
        public bool IsUniform
        {
            get
            {
                return (_verticesPerFace > -1);
            }
        }

        /// <summary>
        /// Returns the faces count.
        /// </summary>
        public int FacesCount
        {
            get
            {
                if (_facesCount > -1)
                    return _facesCount;

                if (_verticesPerFace > -1)
                    return (Indices.Count / _verticesPerFace);

                return VerticesPerPolygon.Count;
            }
        }

        /// <summary>
        /// Gets the list of face-proxy.
        /// You must call BuildFace before using this property.
        /// </summary>
        public RSList<FaceProxy> Faces
        {
            get
            {
                return _faces;
            }
        }

        override public Statistics Statistics
        {
            get
            {
                Statistics statistics = new Statistics();

                statistics.Vertices += Vertices.Count;
                statistics.Faces += FacesCount;

                for (int index = 0; index < Children.Count; index++)
                    statistics.Merge(Children[index].Statistics);

                return statistics;
            }
        }

        #endregion

        #region ClearGeometry

        override public void ClearGeometry()
        {
            base.ClearGeometry();
            Indices.Clear();
            Vertices.Clear();
            if (VerticesPerPolygon != null)
                VerticesPerPolygon.Clear();
            _facesCount = -1;
            _verticesPerFace = -1;
            _faces = null;
            IsUpdatedNormal = false;
            IsUpdatedVertexWinding = true;
            IsOptimized = false;
        }

        #endregion

        #region LevelOfDetail

        /// <summary>
        /// Gets/Sets the level of details.
        /// -1 mean that it use the parent LOD.
        /// </summary>
        public int LevelOfDetail
        {
            get
            {
                if (_LOD < 0)
                {
                    if (Parent.Type != RSType.MeshGeometry)
                        return 5; // default LOD

                    return ((MeshGeometry)Parent).LevelOfDetail;
                }

                return _LOD;
            }
        }

        #endregion

        #region Update

        public override void Update()
        {
            if (!IsOptimized)
            {
                IsOptimized = true;
                Optimize(MeshOptimization.Fast);
            }

            UpdateBoundingBox();

            if (!IsUpdatedVertexWinding)
            {
                IsUpdatedVertexWinding = true;
                UpdateVertexWinding();
            }

            if (!IsUpdatedNormal)
            {
                IsUpdatedNormal = true;
                UpdateNormals();
            }
        }

        #endregion

        #region UpdateBoundingBox

        override public void UpdateBoundingBox()
        {
            base.UpdateBoundingBox();

            for (int index = 0; index < Vertices.Count; index++)
                _boundingBox.Merge(Vertices[index].Coordinate);
        }

        #endregion

        #region Optimize

        /// <summary>
        /// Use this method with precaution.
        /// 
        /// 1 - Check if all the faces have the same number of vertices
        /// 2 - Check for degenerated polygons and remove them
        /// 3 - Check if we can share some vertices between polygons (Full)
        /// </summary>
        private void Optimize(MeshOptimization optimization)
        {
            OptimizeLight();

            if (optimization == MeshOptimization.Fast)
                OptimizeFast();
            else
                OptimizeFull();
        }

        /// <summary>
        /// Check if all the faces have the same number of vertices
        /// </summary>
        private void OptimizeLight()
        {
            if (VerticesPerPolygon != null && VerticesPerPolygon.Count > 0)
            {
                int count = VerticesPerPolygon[0];
                for (int index = 1; index < VerticesPerPolygon.Count; index++)
                    if (count != VerticesPerPolygon[index])
                        return;

                _verticesPerFace = count;
                _facesCount = VerticesPerPolygon.Count;
                VerticesPerPolygon = null;
            }
        }

        /// <summary>
        /// Remove the degenerated polygons (but not the related vertices).
        /// </summary>
        private void OptimizeFast()
        {
            RSList<int> indices = new RSList<int>(3);
            RSList<int> verticesPerPolygon = new RSList<int>();

            BuildFaces();
            int facesCount = 0;
            for (int faceIndex = 0; faceIndex < FacesCount; faceIndex++)
            {
                FaceProxy face = Faces[faceIndex];

                // Surface normal
                Vertex v1 = Vertices[face.Edges[0].Vertex1Indice];
                Vertex v2 = Vertices[face.Edges[0].Vertex2Indice];
                Vertex v3 = Vertices[face.Edges[1].Vertex2Indice];
                Vector3 surfaceNormal = CalculateNormal(v1.Coordinate, v2.Coordinate, v3.Coordinate);

                // Is degenerated or not ?
                if (surfaceNormal.LengthSquared > 0)
                {
                    facesCount++;
                    if (VerticesPerPolygon != null)
                        verticesPerPolygon.Add(VerticesPerPolygon[faceIndex]);
                    for (int edgeIndex = 0; edgeIndex < face.Edges.Count; edgeIndex++)
                    {
                        EdgeProxy e = face.Edges[edgeIndex];
                        indices.Add(e.Vertex1Indice);
                    }
                }
            }

            Indices = indices;
            if (VerticesPerPolygon != null)
                VerticesPerPolygon = verticesPerPolygon;
            if (_facesCount > -1)
                _facesCount = facesCount;
        }

        /// <summary>
        /// Check for degenerated polygons and if we can share some vertices between polygons
        /// </summary>
        private void OptimizeFull()
        {
            RSList<Vertex> vertices = new RSList<Vertex>(3);
            RSList<int> indices = new RSList<int>(3);
            RSList<int> verticesPerPolygon = new RSList<int>(1);

            int indicesStart = 0;
            for (int faceIndex = 0; faceIndex < FacesCount; faceIndex++)
            {
                int verticesCount = VerticesPerFace(faceIndex);

                //---- Is degenerated
                int indice1 = Indices[indicesStart];
                int indice2 = Indices[(indicesStart + 1) % verticesCount];
                int indice3 = Indices[(indicesStart + 2) % verticesCount];

                Vector3 vertex1 = Vertices[indice1].Coordinate;
                Vector3 vertex2 = Vertices[indice2].Coordinate;
                Vector3 vertex3 = Vertices[indice3].Coordinate;

                // if |normal| = 0 -> degenerated
                if (CalculateNormal(vertex1, vertex2, vertex3).LengthSquared != 0)
                {
                    for (int vertexIndex = 0; vertexIndex < verticesCount; vertexIndex++)
                    {
                        int indice = Indices[indicesStart + vertexIndex];
                        Vertex vertex = Vertices[indice];

                        int newIndice = FindVertexIndice(vertices, vertex);
                        if (newIndice < 0)
                        {
                            vertices.Add(vertex);
                            indices.Add(vertices.Count - 1);
                        }
                        else
                            indices.Add(newIndice);
                    }
                    if (VerticesPerPolygon != null)
                        verticesPerPolygon.Add(verticesCount);
                }

                indicesStart += verticesCount;
            }

            // Swap
            Vertices = vertices;
            Indices = indices;
            VerticesPerPolygon = verticesPerPolygon;
        }

        private int FindVertexIndice(RSList<Vertex> vertices, Vertex vertex)
        {
            for (int index = 0; index < vertices.Count; index++)
                if (vertex.Equals(vertices[index]))
                    return index;

            return -1;
        }

        #endregion

        #region UpdateVertexWinding

        /// <summary>
        /// Then take the normal of one of the facets that shares the distant vertex and
        /// compute the dot product of the two vectors. A positive result indicates that
        /// the normals are all correct while a negative result indicates that the normals
        /// are all backwards. If the normals are backwards, negate them all and reverse the
        /// windings of all facets. 
        /// </summary>
        /// <see cref="http://www.opengl.org/resources/code/samples/sig99/advanced99/notes/node16.html"/>
        protected void UpdateVertexWinding()
        {
            int posInIndices = 0;
            for (int index = 0; index < FacesCount; index++)
            {
                int verticesCount = VerticesPerFace(index);

                // Center
                Vector3 polygonCenter = new Vector3();
                for (int index0 = 0; index0 < verticesCount; index0++)
                    polygonCenter += Vertices[Indices[posInIndices + index0]].Coordinate;
                polygonCenter = polygonCenter / verticesCount;

                // Angles
                float[] angles = new float[verticesCount];
                int[] indices = new int[verticesCount];
                Vector3 refVector = Vertices[Indices[posInIndices]].Coordinate - polygonCenter;
                refVector.Normalize();

                angles[0] = 0;
                indices[0] = Indices[posInIndices];

                // Compute the (normalized) vector from the center point (of surface) to this vertex.
                Vector3 referenceNormal = Vertices[indices[0]].Coordinate - _boundingBox.Center;
                referenceNormal.Normalize();

                // Prepare the angles and the indices
                for (int index0 = 1; index0 < verticesCount; index0++)
                {
                    int indice = Indices[posInIndices + index0];
                    Vector3 vertex = Vertices[indice].Coordinate;

                    Vector3 currentVertex = vertex - polygonCenter;
                    currentVertex.Normalize();

                    angles[index0] = refVector.SignedAngle3D(currentVertex, referenceNormal);
                    indices[index0] = indice;
                }

                // Sort the indices by the angles
                Array.Sort(angles, indices, new AngleComparer());
                for (int index0 = 0; index0 < verticesCount; index0++)
                    Indices[posInIndices + index0] = indices[index0];

                posInIndices += verticesCount;
            }
        }

        #endregion

        #region UpdateNormals

        override public void UpdateNormals()
        {
            base.UpdateNormals();

            // No vertice
            if (Indices.Count == 0)
                return;

            // Already calculated
            if (!Vertices[0].Normal.IsInvalid)
                return;

            Vector3[] sum = new Vector3[Vertices.Count];

            int indicesStart = 0;
            for (int index = 0; index < FacesCount; index++)
            {
                int verticesCount = VerticesPerFace(index);
                for (int index0 = 0; index0 < verticesCount; index0++)
                {
                    int indice1 = Indices[indicesStart + index0];
                    int indice2 = Indices[indicesStart + (index0 + 1) % verticesCount];
                    int indice3 = Indices[indicesStart + (index0 + 2) % verticesCount];

                    //---- Calculate the surface normal
                    Vector3 surfaceNormal = CalculateNormal(Vertices[indice1].Coordinate, Vertices[indice2].Coordinate, Vertices[indice3].Coordinate);

                    // Sum it at the vertex index
                    if (!surfaceNormal.IsInvalid)
                        sum[indice2] += surfaceNormal;
                }
                indicesStart += verticesCount;
            }

            for (int index = 0; index < Vertices.Count; index++)
            {
                sum[index].Normalize();
                Vertices.Items[index].Normal = sum[index];
            }
        }

        public void UpdateNormals_ByFace()
        {
            base.UpdateNormals();

            // No vertice
            if (Indices.Count == 0)
                return;

            // Already calculated
            if (!Vertices[0].Normal.IsInvalid)
                return;

            BuildFaces();

            foreach (FaceProxy face in Faces)
            {
                EdgeProxy e1 = face.Edges[0];
                EdgeProxy e2 = face.Edges[1];

                Vertex vertex1 = Vertices[face.Edges[0].Vertex1Indice];
                Vertex vertex2 = Vertices[face.Edges[0].Vertex2Indice];
                Vertex vertex3 = Vertices[face.Edges[1].Vertex2Indice];

                Vector3 surfaceNormal = CalculateNormal(vertex1.Coordinate, vertex2.Coordinate, vertex3.Coordinate);

                foreach (EdgeProxy edge in face.Edges)
                {
                    Vertices.Items[edge.Vertex1Indice].Normal = surfaceNormal;
                    Vertices.Items[edge.Vertex2Indice].Normal = surfaceNormal;
                }
            }

            for (int index = 0; index < Vertices.Count; index++)
                Vertices[index].Normal.Normalize();
        }

        #endregion

        #region BuildFaces

        /// <summary>
        /// Build the faces. Once called you can access the faces by calling the "Faces"
        /// property.
        /// </summary>
        public void BuildFaces()
        {
            _faces = new RSList<FaceProxy>(FacesCount);
            int indiceIndex = 0;

            for (int index0 = 0; index0 < FacesCount; index0++)
            {
                int count = VerticesPerFace(index0);

                FaceProxy face = new FaceProxy(this, index0);
                _faces.Add(face);

                EdgeProxy edge = null;
                for (int index = 0; index < count; index++)
                {
                    int indice = Indices[indiceIndex];

                    if (edge == null)
                    {
                        edge = new EdgeProxy(face);
                        face.Edges.Add(edge);
                    }

                    if (edge.Vertex1Indice < 0)
                    {
                        edge.Vertex1Indice = indice;
                    }
                    else
                    {
                        edge.Vertex2Indice = indice;

                        if (index == count - 1)
                        {
                            // Last 'closing' edge
                            edge = new EdgeProxy(face);
                            face.Edges.Add(edge);
                            edge.Vertex1Indice = indice;
                            edge.Vertex2Indice = face.Edges[0].Vertex1Indice;

                            edge = null;
                        }
                        else
                        {
                            edge = new EdgeProxy(face);
                            face.Edges.Add(edge);
                            edge.Vertex1Indice = indice;
                        }
                    }

                    indiceIndex++;
                }
            }
        }

        #endregion

        #region ReleaseFaces

        /// <summary>
        /// Release all the faces.
        /// </summary>
        public void ReleaseFaces()
        {
            _faces = null;
        }

        #endregion

        #region ToString

        public override string ToString()
        {
            return Name;
        }

        #endregion

        #region Helpers

        /// <summary>
        /// Calculate the normal based on 3 points in space.
        /// 
        /// Reference :
        /// "Generating Vertex Normals" by Max Wagner, mwagner@digipen.edu
        /// "Generating Model Normals" : http://www.opengl.org/resources/code/samples/sig99/advanced99/notes/node15.html
        /// </summary>
        internal Vector3 CalculateNormal(Vector3 point1, Vector3 point2, Vector3 point3)
        {
            Vector3 e1 = point1 - point2;
            Vector3 e2 = point3 - point2;

            //Vector3 normal = e1.Cross(e2);
            Vector3 normal = e2.Cross(e1);
            normal.Normalize();

            //if (normal.Length < 0.9 || normal.Length > 1.1)
            //    normal = Vector3.UnitZ.Clone();

            // --------------------------------------------------
            // One problem with the existing approach is that, for surfaces that were actually not meant
            // to be smooth (i.e., a mesh of a cube), the result will appear strange; at the corners of a
            // sharp crease, the lighting will appear smooth, which is clearly not what we want.
            // One approach to combat this is to use a threshold when deciding whether to include a
            // triangle’s normal in the averaging.
            // Specifically, when examining the ith vertex, we cache
            // the surface normal of the triangle to which the vertex technically belongs (as opposed to
            // the triangles which share a copy of the vertex elsewhere in the triangle list). Then, when
            // upon finding another triangle that shares the vertex, we compute the dot product between
            // the cached normal and the current triangle’s normal; if this dot product is less than some
            // threshold (call it ε, usually a little above 0), then we do not include the current triangle’s
            // normal in the average. How does this work? Recall that the dot product corresponds to
            // the cosine of the angle between two vectors. What we are effectively saying is, if the
            // angle between two surfaces is greater than ε, don’t average them.
            // --------------------------------------------------

            // e3 = another vertice of the geometry
            //if (e1.Dot(e3) < 0.01)
            //    return Vector3.Invalid;

            // --------------------------------------------------
            // Another possible improvement to our algorithm comes from examining the fact that,
            // while a vertex lies at the intersection of multiple triangles, these triangles are not
            // necessarily of equal size. Some people suggest using the area of the triangle as a
            // weighting factor when including a surface normal in the averaging process. The
            // pseudocode is hardly changed to incorporate this; we just require a new routine to
            // compute the area of a triangle, given the three vertices.
            // --------------------------------------------------

            // normal *= Area(this);

            return normal;
        }

        #endregion

        #region class : AngleComparer

        class AngleComparer : System.Collections.IComparer
        {
            public int Compare(object x, object y)
            {
                return (int)(((float)x) - ((float)y));
            }
        }

        #endregion

        #region Clone

        override public Geometry Clone()
        {
            MeshGeometry clone = new MeshGeometry(Parent);
            base.Clone(clone);

            clone.Vertices = new RSList<Vertex>(Vertices);

            clone.Indices = new RSList<int>(Indices);
            if (VerticesPerPolygon != null)
                clone.VerticesPerPolygon = new RSList<int>(VerticesPerPolygon);

            clone.IsUpdatedNormal = IsUpdatedNormal;
            clone.IsUpdatedVertexWinding = IsUpdatedVertexWinding;
            clone.IsOptimized = IsOptimized;
            clone._facesCount = _facesCount;
            clone._verticesPerFace = _verticesPerFace;
            clone._LOD = _LOD;

            return clone;
        }

        #endregion

    }

}
